#lang racket

(require math/bigfloat)

(bf-precision 1000)

(define (factoring N)
  (factor-mul N))

(define (factor-mul N)
  (define M (bfceiling (bfsqrt N)))
  (define sqrtA (bffloor (bfsqrt (bf- (bf* M M) N))))
  (define u (bf+ M sqrtA))
  (define v (bf- M sqrtA))
  (define r (factored N u v))
  (displayln (list N u v))
  (if (equal? r #t)
      (displayln (list N M sqrtA u v))
      (if (bf> (bf/ (car r) (cdr r)) (bf/ u v))
          (factor-mul (bf* N u v))
          (factor-mul N (bf+ M 1.bf)))))

(define (factored N u v)
  (define theN (bf* N u v))
  (define M (bfceiling (bfsqrt theN)))
  (define a (bf- (bf* M M) N))
  (define sqrtA (bffloor (bfsqrt a)))
  (if (bf= (bf* sqrtA sqrtA) a)
      #t
      (cons (bf+ M sqrtA) (bf- M sqrtA))))

(factoring (bf 20159))

;(bf/ (bf 27279640754692463755502939700848285) (bf 165165494642325661))


